Corelab Seminar
2011-2012
Vassilis Nakos (NTUA)
A polylogarithmic-competitive algorithm for the k-server problem.
Abstract.
The k-server problem is one of the most fundamental and extensively studied problems in online computation. Suppose there is a n-point metric space and k servers are initially located at some of the points of the metric space. At each time step, a request arrives and this request is served by moving a server to the requested point. The goal is to minimize the total distance travelled by the servers. It is a conjecture that there is a k-competitive algorithm for the online k-server. Koutsoupias and Papadimitriou firstly proved that the work-function algorithm (building an algorithm based on the dynamic programming equation on the requests seen so far) is (2k-1)-competitive. However,although randomization is a strong tool in online computation , no randomized algorithm that achieves a sub-linear in the number of servers competitive ratio was known(in the general case). In this paper Bansal,Buchbinder,Madry and Naor propose the first randomized polylogarithmic-competitive algorithm for the problem on a general metric with a finite number of points, combining ideas from a paper of Cote and Meyerson. Firstly,using standard techniques they embed the metric space to another more suitable losing only a logarithmc fraction of the optimal solution. Then, they attempt to give an algorithm for the fractional instance of the problem, using a reduction of the problem to the Allocation Problem, which was presented in another paper of theirs. They complete their algorithm with a randomized rounding scheme that rounds the fractional algorithm to a feasible solution while multiplying the total cost by a constant factor.